#!/usr/bin/python
#-*- coding:utf-8 -*-
# Description:  <C程序设计竞赛实训教程> 刘高军、何丽 编著 第11.2节：迷宫问题
#          0代表通路， 1代表墙，找到穿越迷宫的一条路径
#  for breadth first search, 采用广度优先搜索算法，数据结构除了需要记录当前节点，也需要
#  记录前一个节点的坐标

import numpy as np
from pprint import pprint
from collections import deque, namedtuple
node = namedtuple('NODE', ['current', 'previous'])
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]

def seek(p, m, mark):
    target_point = m.shape[0] - 2, m.shape[1] - 2
    mark = np.zeros_like(m, dtype=bool)
    mark[p] = True
    start_node = node(p, None)
    que = [start_node]
    stack = deque()
    found = False
    while que:
        n = que.pop(0)
        if n.current == target_point:
            found = True
            break
        stack.appendleft(n)
        for i, j in move:
            nxt = node((n.current[0] + i, n.current[1] + j), n.current)
            if m[nxt.current]==0 and not mark[nxt.current] :
                mark[nxt.current] = True
                que.append(nxt)
    if found:
        path = []
        top = n
        i = 0
        while top.previous : # 在stack中倒退逐个寻找路径上的点，然后逆序之后输出
            if stack[i].current == top.previous:
                path.append(top.current)
                top = stack[i]
            i+=1
        path.append(top.current)
        print(list(reversed(path)))
    else :
        print 'Failed to find a path'
            
    
def search(maze) :
    col = np.ones((maze.shape[0], 1), dtype=int)
    m = np.hstack([col, maze, col])
    row = np.ones((1, m.shape[1]), dtype=int)
    m = np.vstack([row, m, row])
    mark = np.zeros_like(m, dtype=bool)
    seek((1,1), m, mark)

if __name__ == '__main__':
    maze = np.array([
        [0, 0, 1, 0, 0, 0, 1, 1,],
        [1, 0, 0, 0, 1, 0, 0, 0,],
        [0, 0, 0, 1, 1, 0, 1, 1,],
        [1, 1, 0, 1, 0, 0, 0, 0,],
        [0, 0, 0, 0, 0, 1, 0, 1,],
        [1, 0, 1, 0, 0, 0, 0, 0,],
    ], dtype=int)

    pprint(maze)
    search(maze)
